import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * 大根堆 堆的父节点都大于他的俩个子节点 优先级队列
 */
public class MyPriorityQueue {
    int[] array;
    int userSize;

    public MyPriorityQueue() {
        array = new int[1];
        userSize = 0;
    }

    //构造方法
    public MyPriorityQueue(int[] arr) {
        this.array = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            this.array[i] = arr[i];
            userSize++;
        }
    }

    //获取堆顶元素
    public int peek() {
        return array[0];
    }
    //向下交换
    public int[] creatHeap() {
        for (int i = array.length-1; i >= 0; i--) {//每个元素都要遍历 包括堆顶
            shiftDwon(i, userSize);
        }
        return array;
    }

    /**
     * 根节点大于子类节点
     * @param parent   这个是父类节点 数据是往下交换的所以是向下交换
     * @param userSize 这个是说明这个树交换终止的条件
     */
    private void shiftDwon(int parent, int userSize) {
        int child = parent*2+1;//这个是父节点的左节点
        while (child < userSize) {
            if ((child+1) < userSize && array[child] < array[child + 1]) {
                child++;//走到更大的右节点
            }
            if (array[child] > array[parent]) {//交换 大根堆
                swap(array, child, parent);
                parent = child;
                child = child*2+1;//走到下 一个左节点
            }else {//说明调整好了
                break;
            }
        }
    }
    //堆的插入
    public void push(int val) {
        if(isFull()){
            array = Arrays.copyOf(array, 2 * array.length);
        }
        array[userSize++] = val;
        shiftUp(userSize-1);

    }

    //堆的删除  删除的是堆顶元素
    public void poll(int[] array) {
        //将堆头的尾巴交换
        swap(array, 0, userSize - 1);
        userSize--;
        shiftDwon(0,userSize);//从堆顶这里开始
    }
    /**
     * 建立的是大根堆
     * @param child
     */
    public void shiftUp(int child) {
        //
        int parent =(child-1) / 2 ;
        while (child > 0) {
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                child = parent;
                parent = (child - 1) / 2;//走到父节点
            } else {
                break;
            }
        }
    }

    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private boolean isFull() {

        return userSize == array.length;
    }

    public void heapSort(){
        int tmp = userSize;
        System.out.println("---");
        while(userSize > 0){
            creatHeap();//这个是一次就能找到最大了吗
            swap(array,0,userSize-1);//指向的是最后一个元素的下表
            //因为是大根堆，所以堆顶元素是最大的，所以让堆顶元素和数组的最后一个位置进行交换， 这样最大的元素就是有序的了
            //然后，usedsize-1 将剩下的数组重新调整一下，让他重新恢复到大根堆。重复这个流程即可
            //了解了
            userSize--;
        }
        userSize = tmp;
//        Collections.reverse(Arrays.asList(array));
//        System.out.println(" hhh"+Arrays.asList(array).toArray());
    }
}

class text{
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        MyPriorityQueue hh = new MyPriorityQueue(arr);
//        for (int i = 1; i < 9; i++) {
//            hh.push(i);
//        }
        hh.creatHeap();


        PriorityQueue<Integer> hhh = new PriorityQueue<>();
        hhh.add(1);
        hhh.offer(2);
        hhh.poll();


        System.out.println(-1 / 2);

    }
}